Consensus with Link Failures/Packet LossesConsensus with random link failures is a prototype problem for studying the dynamics of stochastic networks. In its simplest form, this problem can be recast as linear systems with multiplicative noise, or equivalently as uncertain systems with structured stochastic uncertainty. Such systems can exhibit complex phenomena such as heavy tailed distributions and Levy flights, yet are more tractable than completely general stochastic systems. The network settingConsider a consensus algorithm over a network in which links randomly fail at each round. These link failures can represent either communication failures between nodes andor packet losses. We thus have a consensus algorithm over a type of stochastic network/. This setting is caricatured in the following animated diagram (red color depicts failing links).
The system theory reformulationA nice feature of this problem is that the dynamics of the standard average consensus algorithm over a network with link failures can be recast as a linear system with multiplicative noise. The dynamics look like this where the deltas are iid bernouli random variables representing the failures of each of the n links. The B matrices represent the effect of each link's disconnection on the algorithm's dynamics. This is now a stochastic system, but a recursion equation for the covariance of the state can be derived to be where the sigmas are the variances of each of the deltas. The actual recursion we use is a little different since one needs to keep track of the covariances of the deviation from average state, rather than the actual state, but the basic idea is similar. All second order convergence properties of the stochastic system (such as rates of convergece of variances) can be deduced from studying this matrix recursion equation. The mathematical tools usedConvergence properties of the covariance recursion are determined by studying the Lyapunov-like matrix-valued operator For example, the eigenvalues of this operator determine the convergence rate of variances. In general, there is no simple relationship between the eigenvalues of this operator and the spectral properties of the original matrices (e.g. one cannot easily relate the second smallest graph Laplacian eigenvalue, or the Fiedler vector, to the eigenvalues of this operator). Our approach is to use spectral perturbation theory and derive the convergence rates up to first order in the probability of failure. For certain regular graph structures, we can obtain explicit expressions for these rates. Reformulation as a stochastic structured uncertainty problemProblems with multiplicative uncertainty can be viewed in a unified manner as structured uncertainty problems as shown in the diagram below.
Related Papers
Related Talks
|